package algorithm;

import com.google.common.base.Joiner;
import reactor.core.publisher.Flux;

import java.util.*;

/**
 * @program: util
 * @description: 合并N个有序链表
 * 模拟两个有序链表的插入排序
 * @author: zhouliangliang
 * @create: 2021-05-13 20:38
 **/
public class SortedListMerge {

    Random random = new Random();

    /**
     * 产生n个有序链表
     * 每个有序链表不少于m个元素
     */
    public List<List<Integer>> generate(int n, int m) {
        List<List<Integer>> list = new LinkedList<>();

        for(int i=0; i<n; i++) {
            int start = random.nextInt(1000);
            int end = Math.abs(random.nextInt()) % m;
            List<Integer> genlist = Flux.range(start, end).collectList().block();
            list.add(genlist);
        }

        return list;
    }

    /**
     * 输出元素
     */
    private void output(List<List<Integer>> list) {
        list.forEach(item->{
            System.out.println(Joiner.on(",").join(item));
        });
        System.out.println();
    }

    public void merge(List<List<Integer>> list) {

        //计算总共有多少个元素
        int total = list.stream().map(item->{
            return item.size();
        }).reduce((a,b)-> a + b).get();

        //存储合并后的链表元素
        List<Integer> mergeArray = new ArrayList<>(total);

        //初始化每一个有序链表的头指针和链表元素数量
        int [][]array = new int[list.size()][2];

        for(int i=0;i<array.length; i++) {
            array[i][0] = 0; //首元素引用
            array[i][1] = list.get(i).size(); //元素个数
        }

        //输出验证
        for(int i=0; i<array.length; i++) {
            for(int j=0; j<array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }

        while(getFlag(array)) {
            //最小元素的那个链表的下标
            int index = Integer.MAX_VALUE;
            //最小的元素
            int value = Integer.MAX_VALUE;

            for(int i=0; i<list.size(); i++) {
                if(array[i][0] < array[i][1] && list.get(i).get(array[i][0]) < value) {
                    index = i;
                    value = list.get(i).get(array[i][0]);
                }
            }

            array[index][0] = array[index][0] + 1;
            mergeArray.add(value);
        }

        System.out.println(Joiner.on(",").join(mergeArray));
    }

    /**
     * 判断是不是有链表没有到头
     * @param array
     */
    private boolean getFlag(int [][] array) {
        for(int i=0; i<array.length; i++) {
            if(array[i][0] < array[i][1]) {
                return true;
            }
        }
        return false;
    }

//    public void test() {
//        for(int i=0; i<20; i++) {
//            System.out.println(random.nextInt(10));
//        }
//
//    }

    public static void main(String[] args) {
        SortedListMerge slm = new SortedListMerge();
        List<List<Integer>> list = slm.generate(3,10);
        slm.output(list);
        slm.merge(list);


//        List<List<Integer>> list  = new LinkedList<>();
//        List<Integer> list1 = new ArrayList<>(2);
//        list1.add(1);
//        list1.add(2);
//        List<Integer> list2 = new ArrayList<>(3);
//        list2.add(1);
//        list2.add(2);
//        list2.add(3);
//        list.add(list1);
//        list.add(list2);
//        new SortedListMerge().merge(list);
    }
}
